/**
 * 1）单链表的插入、删除、查找操作
 * https://c.biancheng.net/view/8105.html
 */
export class Node {
  public data: any;
  public next: Node | null;
  constructor(data: any) {
    this.data = data;
    this.next = null;
  }
}

export default class LinkedList {
  /** 头节点 */
  private head: Node;

  constructor() {
    this.head = new Node('head');
  }

  /** 尾部添加节点 */
  append(data: number) {
    let currentNode = this.head;

    // 找到最后一个节点
    while (currentNode.next) {
      currentNode = currentNode.next;
    }

    const newNode = new Node(data);

    currentNode.next = newNode;
  }

  // 根据value查找节点
  findByValue(value: number) {
    let currentNode = this.head;
    while (currentNode && currentNode.data != value) {
      // if (currentNode.data == value) {
      //   break;
      // }
      currentNode = currentNode.next;
    }

    console.log(currentNode);
  }

  // 根据index查找节点，下标从0开始
  findByIndex(index: number) {
    let pos = 0;
    let currentNode = this.head;

    while (pos != index && currentNode) {
      pos++;
      currentNode = currentNode.next;
    }

    console.log(currentNode);
  }

  // 指定元素向后插入
  insert(ele: number, data: number) {
    // 找到指定元素
    let currentNode = this.head;
    while (currentNode && currentNode.data != ele) {
      currentNode = currentNode.next;
    }

    // 元素不存在
    if (!currentNode) {
      console.log('链表中不存在指定元素', ele);
      return;
    }

    const newNode = new Node(data);

    newNode.next = currentNode.next;
    currentNode.next = newNode;

    return newNode;
  }

  // 查找前一个
  findPre(value: number) {
    let currentNode = this.head;

    // 如果不存在元素，循环完 currentNode 等于最后一个节点
    while (currentNode && currentNode.next && currentNode.next.data != value) {
      currentNode = currentNode.next;
    }

    // 如果是最后一个元素 返回-1
    return currentNode.next == null ? -1 : currentNode;
  }

  // 根据值删除
  delByValue(value: number) {
    // 查找前一个元素
    const preNode = this.findPre(value);

    if (preNode != -1) {
      preNode.next = preNode.next.next;
    } else {
      console.log('不存在该节点');
    }
  }

  // 打印链表
  print() {
    let currentNode = this.head;
    while (!!currentNode) {
      console.log(currentNode.data);
      currentNode = currentNode.next;
    }
  }

  /**
   * 就地逆置法
   * 原理说明
   * 假设当前节点是p
   * p得下一个节点是a
   * a得下一个节点是b
   * 将a节点删除，p->next = b
   * 将a节点添加到头节点
   * 将头节点复制给a
   * 将p赋值下一个节点
   */
  rever() {
    let beg = this.head;
    let end = this.head.next;

    while (end) {
      // 删除 end 节点

      beg.next = end.next;

      end.next = this.head;
      this.head = end;

      end = beg.next;
    }
  }

  /**
   * 遍历法
   * 使用3个变量
   * 其中 beg = null，mid = head, end = head->next
   * 中间节点指向开始节点
   * 然后将中间赋值给开头节点，尾节点复制给中间节点
   * beg = mid,mid = end,end = end-> next
   * 循环到end == null 结束
   * 将mid赋值给head
   */
  each_rever() {
    let beg = null;
    let mid = this.head;
    let end = this.head.next;
    while (1) {
      mid.next = beg;

      if (end == null) {
        break;
      }

      beg = mid;
      mid = end;
      end = end.next;
    }
    this.head = mid;
  }
}

const linkedList = new LinkedList();

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);
linkedList.print();

// linkedList.findByValue(3);
// linkedList.findByIndex(2);

// linkedList.insert(2, 6);
// linkedList.print();

// linkedList.findPre(3);
// linkedList.findPre(30);

// linkedList.delByValue(4);
// linkedList.print();

linkedList.rever();
// linkedList.each_rever();
linkedList.print();
